/**
 * Copyright (C) 2008+ Saifeng Zeng
 *		 2008+ Spark Zheng
 *
 * @file	include/bit.h
 * @brief 
 *      Bit module, A basic datastruct module.
 *      Memory-free operations, bit-vectors datastruct and atomic algorithms
 *      -1. bit vector
 *      -2. atomic
 *
 * @module      dlib
 * @see		dlib
 *
 * @history	version 0.1.0, Saifeng initialized.
 *		version 0.1.2, Spark add dlib_show_bytes(like in cs:app)
 *		version 0.3.0, Spark add atomic operations.
 */

#ifndef _DLIB_BIT_H
#define _DLIB_BIT_H

#ifdef __cplusplus
extern "C" {
#endif

#include "global.h"
#include "lock.h"

/** 32 bit operations */
/**
 * simple bit operations:
 * @param x, source
 * @param n, bit number( 1100110010101010, the right bit is first bit )
 */
#define DLIB_TEST_BIT(x, n)		((x) & (1U << ((n) - 1)))
#define DLIB_SET_BIT(x, n)		(x) |= (1U << ((n) - 1))
#define DLIB_CLEAR_BIT(x, n)		(x) &= ~(1U << ((n) - 1))
#define DLIB_REVERSE_BIT(x, n)		(x) ^= (1U << ((n) - 1))

/** set the first argument's last n bits zero, one or reverse */
#define DLIB_SET_END_ZERO(x, n)		(x) &= ~0U << (n)
#define DLIB_SET_END_ONE(x, n)		(x) |= ~(~0U << (n))
#define DLIB_SET_END_REVERSE(x, n)	(x) ^= ~(~0U << (n))

/** set the first argument's n bit to m bit zero, one or reverse (n > m) */
#define DLIB_SET_SEGMENT_ZERO(x, n, m) \
	(x) &= (~(~0U << (m))) | (~0U << (n))
#define DLIB_SET_SEGMENT_ONE(x, n, m) \
	(x) |= (~(~0U << (m))) ^ (~(~0U << (n)))
#define DLIB_SET_SEGMENT_REVERSE(x, n, m) \
	(x) ^= (~((~0U << (m))) ^ (~(~0U << (n))))
	
/** shift right or left */
/** logic shift */
#define DLIB_SHR_WITH_ZERO(x, n) \
	({(x) >>= (n); DLIB_SET_SEGMENT_ZERO((x), 32, (32 - (n)));})
#define DLIB_SHL_WITH_ZERO(x, n)	(x) <<= (n)
#define DLIB_SHR_WITH_ONE(x, n) \
	({(x) >>= (n); DLIB_SET_SEGMENT_ONE((x), 32, (32 - (n)));})
#define DLIB_SHL_WITH_ONE(x, n) \
	({(x) <<= (n); DLIB_SET_END_ONE((x), (n));})
#define DLIB_SHR(x, n)		DLIB_SHR_WITH_ZERO(x, n)
#define DLIB_SHL(x, n)		DLIB_SHL_WITH_ZERO(x, n)

/** arithmetical shift */
#define DLIB_SAR(x, n) \
	(DLIB_TEST_BIT(x, 32) ? DLIB_SHR_WITH_ONE(x, n) : DLIB_SHR_WITH_ZERO(x, n))
#define DLIB_SAL(x, n)		(x) <<= (n)

/** loop shift */
#define DLIB_ROR(x, n)		(x) = (x) >> (n) | (x) << (32 - (n))
#define DLIB_ROL(x, n)		(x) = (x) >> (32 - (n)) | (x) << (n)

/** get the first argument's last n bits */
#define DLIB_GET_RIGHT(x, n)	(x) &= (~(~0U << (n)))

/** set the right ones to zero, as 1110111 => 1110000 */
#define DLIB_CLEAR_RIGHT_ONES(x)	(x) &= (x) + 1
/** set the right zeros to one, as 1010100 => 1010111 */
#define DLIB_SET_RIGHT_ZEROS(x)		(x) |= (x) - 1
	
/** count the 1's frequency in binary number, as 10101001 => 4 */
#define DLIB_COUNT_ONES(x, r)	do { \
	(r) = (x); \
	(r) = ((r) & 0x55555555) + (((r) >>  1) & 0x55555555); \
	(r) = ((r) & 0x33333333) + (((r) >>  2) & 0x33333333); \
	(r) = ((r) & 0x0F0F0F0F) + (((r) >>  4) & 0x0F0F0F0F); \
	(r) = ((r) & 0x00FF00FF) + (((r) >>  8) & 0x00FF00FF); \
	(r) = ((r) & 0x0000FFFF) + (((r) >> 16) & 0x0000FFFF); } while (0)

/** inverted sequence of a binary number */
#define DLIB_INVERTED_SEQUENCE(x, r)	do { \
	(r) = (x); \
	(r) = ((r) & 0x55555555) <<  1 | ((r) & 0xAAAAAAAA) >>  1; \
	(r) = ((r) & 0x33333333) <<  2 | ((r) & 0xCCCCCCCC) >>  2; \
	(r) = ((r) & 0x0F0F0F0F) <<  4 | ((r) & 0xF0F0F0F0) >>  4; \
	(r) = ((r) & 0x00FF00FF) <<  8 | ((r) & 0xFF00FF00) >>  8; \
	(r) = ((r) & 0x0000FFFF) << 16 | ((r) & 0xFFFF0000) >> 16; } while (0)

/** FFS: returns the position of the lowest 1 */
#define DLIB_FAST_FFS(x, r)		do { \
	register uint32_t __x, __bits = 32; \
	if (x) { \
		__x = (x); \
		--__bits; \
		if (__x & 0x0000FFFF) { __x &= 0x0000FFFF; __bits -= 16;} \
		if (__x & 0x00FF00FF) { __x &= 0x00FF00FF; __bits -=  8;} \
		if (__x & 0x0F0F0F0F) { __x &= 0x0F0F0F0F; __bits -=  4;} \
		if (__x & 0x33333333) { __x &= 0x33333333; __bits -=  2;} \
		if (__x & 0x55555555) { __x &= 0x55555555; __bits -=  1;} \
	} \
	(r) = __bits; } while (0)

/** FLS: returns the position of the highest 1 */
#define DLIB_FAST_FLS(x, r)		do { \
	register uint32_t __x, __bits = 0; \
	if (x) { \
		 __x = (x); \
		if (__x & 0xFFFF0000) { __x &= 0xFFFF0000; __bits += 16;} \
		if (__x & 0xFF00FF00) { __x &= 0xFF00FF00; __bits +=  8;} \
		if (__x & 0xF0F0F0F0) { __x &= 0xF0F0F0F0; __bits +=  4;} \
		if (__x & 0xCCCCCCCC) { __x &= 0xCCCCCCCC; __bits +=  2;} \
		if (__x & 0xAAAAAAAA) { __x &= 0xAAAAAAAA; __bits +=  1;} \
    	} else { \
		__bits = 32; \
	} \
	(r) = __bits; } while (0)

/** 64 bit operations */
/**
 * simple bit operations:
 * @param x, source
 * @param n, bit number( 1100110010101010, the right bit is first bit )
 */
#define DLIB_TEST_BIT64(x, n)		((x) & (1ULL << ((n) - 1)))
#define DLIB_SET_BIT64(x, n)		(x) |= (1ULL << ((n) - 1))
#define DLIB_CLEAR_BIT64(x, n)		(x) &= ~(1ULL << ((n) - 1))
#define DLIB_REVERSE_BIT64(x, n)	(x) ^= (1ULL << ((n) - 1))

/** set the first argument's last n bits zero, one or reverse */
#define DLIB_SET_END_ZERO64(x, n)	(x) &= ~0ULL << (n)
#define DLIB_SET_END_ONE64(x, n)	(x) |= ~(~0ULL << (n))
#define DLIB_SET_END_REVERSE64(x, n)	(x) ^= ~(~0ULL << (n))

/** set the first argument's n bit to m bit zero, one or reverse (n > m) */
#define DLIB_SET_SEGMENT_ZERO64(x, n, m) \
	(x) &= (~(~0ULL << (m))) | (~0ULL << (n))
#define DLIB_SET_SEGMENT_ONE64(x, n, m) \
	(x) |= (~(~0ULL << (m))) ^ (~(~0ULL << (n)))
#define DLIB_SET_SEGMENT_REVERSE64(x, n, m) \
	(x) ^= (~((~0ULL << (m))) ^ (~(~0ULL << (n))))
	
/** shift right or left */
/** logic shift */
#define DLIB_SHR_WITH_ZERO64(x, n) \
	({(x) >>= (n); DLIB_SET_SEGMENT_ZERO64((x), 64, (64 - (n)));})
#define DLIB_SHL_WITH_ZERO64(x, n)	(x) <<= (n)
#define DLIB_SHR_WITH_ONE64(x, n) \
	({(x) >>= (n); DLIB_SET_SEGMENT_ONE64((x), 64, (64 - (n)));})
#define DLIB_SHL_WITH_ONE64(x, n) \
	({(x) <<= (n); DLIB_SET_END_ONE64((x), (n));})
#define DLIB_SHR64(x, n)		DLIB_SHR_WITH_ZERO64(x, n)
#define DLIB_SHL64(x, n)		DLIB_SHL_WITH_ZERO64(x, n)

/** arithmetical shift */
#define DLIB_SAR64(x, n) \
	DLIB_TEST_BIT(x, 64) ? DLIB_SHR_WITH_ONE64(x, n) : DLIB_SHR_WITH_ZERO64(x, n)
#define DLIB_SAL64(x, n)		(x) <<= (n)

/** loop shift */
#define DLIB_ROR64(x, n)		(x) = (x) >> (n) | (x) << (64 - (n))
#define DLIB_ROL64(x, n)		(x) = (x) >> (64 - (n)) | (x) << (n)

/** get the first argument's last n bits */
#define DLIB_GET_RIGHT64(x, n)		(x) &= (~(~0ULL << (n)))

/** set the right ones to zero, as 1110111 => 1110000 */
#define DLIB_CLEAR_RIGHT_ONES64(x)	(x) &= (x) + 1
/** set the right zeros to one, as 1010100 => 1010111 */
#define DLIB_SET_RIGHT_ZEROS64(x)	(x) |= (x) - 1

/** count the 1's frequency in binary number, as 10101001 => 4 */
#define DLIB_COUNT_ONES64(x, r)	do { \
	(r) = (x); \
	(r) = ((r) & 0x5555555555555555ULL) + (((r) >>  1) & 0x5555555555555555ULL); \
	(r) = ((r) & 0x3333333333333333ULL) + (((r) >>  2) & 0x3333333333333333ULL); \
	(r) = ((r) & 0x0F0F0F0F0F0F0F0FULL) + (((r) >>  4) & 0x0F0F0F0F0F0F0F0FULL); \
	(r) = ((r) & 0x00FF00FF00FF00FFULL) + (((r) >>  8) & 0x00FF00FF00FF00FFULL); \
	(r) = ((r) & 0x0000FFFF0000FFFFULL) + (((r) >> 16) & 0x0000FFFF0000FFFFULL); \
	(r) = ((r) & 0x00000000FFFFFFFFULL) + (((r) >> 32) & 0x00000000FFFFFFFFULL); \
	} while (0)

/** inverted sequence of a binary number */
#define DLIB_INVERTED_SEQUENCE64(x, r)	do { \
	(r) = (x); \
	(r) = ((r) & 0x5555555555555555ULL) <<  1 | ((r) & 0xAAAAAAAAAAAAAAAAULL) >>  1; \
	(r) = ((r) & 0x3333333333333333ULL) <<  2 | ((r) & 0xCCCCCCCCCCCCCCCCULL) >>  2; \
	(r) = ((r) & 0x0F0F0F0F0F0F0F0FULL) <<  4 | ((r) & 0xF0F0F0F0F0F0F0F0ULL) >>  4; \
	(r) = ((r) & 0x00FF00FF00FF00FFULL) <<  8 | ((r) & 0xFF00FF00FF00FF00ULL) >>  8; \
	(r) = ((r) & 0x0000FFFF0000FFFFULL) << 16 | ((r) & 0xFFFF0000FFFF0000ULL) >> 16; \
	(r) = ((r) & 0x00000000FFFFFFFFULL) << 32 | ((r) & 0xFFFFFFFF00000000ULL) >> 32; \
	} while (0)

/** FFS: returns the position of the lowest 1 on 64 bit */
#define DLIB_FAST_FFS64(x, r)		do { \
	register uint32_t __bits = 64; \
	register uint64_t __x = ((x) >> 32); \
	if ((x) & 0xFFFFFFFFULL) { \
		 __x = (x) & 0xFFFFFFFFULL; \
		__bits -= 32; \
	} \
	if (__x) { \
		 __bits--; \
		if (__x & 0x0000FFFFULL) { __x &= 0x0000FFFFULL; __bits -= 16;} \
		if (__x & 0x00FF00FFULL) { __x &= 0x00FF00FFULL; __bits -=  8;} \
		if (__x & 0x0F0F0F0FULL) { __x &= 0x0F0F0F0FULL; __bits -=  4;} \
		if (__x & 0x33333333ULL) { __x &= 0x33333333ULL; __bits -=  2;} \
		if (__x & 0x55555555ULL) { __x &= 0x55555555ULL; __bits -=  1;} \
	} \
	(r) = __bits; } while (0)

/** FLS: returns the position of the highest 1 on 64 bit */
#define DLIB_FAST_FLS64(x, r)		do { \
	register uint32_t __bits = 0; \
	register uint64_t __x = (x); \
	if (((uint64_t)(x)) >> 32) { \
		__x = ((uint64_t)(x)) >> 32; \
		__bits += 32; \
	} \
	if (__x) { \
		if (__x & 0xFFFF0000ULL) { __x &= 0xFFFF0000ULL; __bits += 16;} \
		if (__x & 0xFF00FF00ULL) { __x &= 0xFF00FF00ULL; __bits +=  8;} \
		if (__x & 0xF0F0F0F0ULL) { __x &= 0xF0F0F0F0ULL; __bits +=  4;} \
		if (__x & 0xCCCCCCCCULL) { __x &= 0xCCCCCCCCULL; __bits +=  2;} \
		if (__x & 0xAAAAAAAAULL) { __x &= 0xAAAAAAAAULL; __bits +=  1;} \
	} else { \
		__bits += 32; \
	} \
	(r) = __bits; } while (0)


/**
 * Atomic module
 * @brief
 *      struct dlib_atomic_t
 *      atomic_APIs
 */
#if (defined (__i386__) || defined (__x86_64__)) && (defined (__GNUC__))
#define atomic_memory_barrier()    __asm__ __volatile__ ("" ::: "memory")
/** old as does not support "pause" opcode */
#define atomic_cpu_pause()	 __asm__ (".byte 0xf3, 0x90")

typedef struct dlib_atomic {
	volatile long   atom;
} dlib_atomic_t;

static inline int dlib_atomic_init(dlib_atomic_t *arg, long val)
{
	arg->atom = val;
	return 0;
}

static inline void dlib_atomic_exit(dlib_atomic_t *arg)
{
	arg->atom = 0;
}

static inline int dlib_atomic_test(dlib_atomic_t *arg, long test)
{
	return (arg->atom == test);
}

static inline void dlib_atomic_set(dlib_atomic_t *arg, long val)
{
	arg->atom = val;
}

static inline long dlib_atomic_get(dlib_atomic_t *arg)
{
	return arg->atom;
}

static inline void dlib_atomic_inc(dlib_atomic_t *arg)
{
	__asm__ __volatile__("lock; incl %0"
			     : "=m"(arg->atom)
			     : "m"(arg->atom)
			     : "memory");
}

static inline void dlib_atomic_dec(dlib_atomic_t *arg)
{
	__asm__ __volatile__("lock; decl %0"
			     : "=m"(arg->atom)
			     : "m"(arg->atom)
			     : "memory");
	return;
}

static inline void dlib_atomic_add(dlib_atomic_t *arg, long add)
{
	__asm__ __volatile__ ("lock; addl %1, %0"
			      : "=m"(arg->atom)
			      : "r"(add), "m"(arg->atom)
			      : "memory", "cc");
	return;
}

static inline void dlib_atomic_sub(dlib_atomic_t *arg, long sub)
{
	__asm__ __volatile__ ("lock; subl %1, %0"
			      : "=m"(arg->atom)
			      : "r"(sub), "m"(arg->atom)
			      : "memory", "cc");
	return;
}

static inline long dlib_atomic_xadd(dlib_atomic_t *arg, long add)
{
	__asm__ __volatile__ ("lock; xaddl %0, %1"
			      : "=r"(add), "=m"(arg->atom)
			      : "0"(add), "m"(arg->atom)
			      : "memory", "cc");
	return add;
}

static inline long dlib_atomic_xsub(dlib_atomic_t *arg, long sub)
{
	long add = 0 - sub;
	__asm__ __volatile__ ("lock; xaddl %0, %1"
			      : "=r"(add), "=m"(arg->atom)
			      : "0"(add), "m"(arg->atom)
			      : "memory", "cc");
	return add;
}

static inline long dlib_atomic_xand(dlib_atomic_t *arg, long mask)
{
	long ret = arg->atom;
	
	__asm__ __volatile__ ("lock; cmpxchgl %2, %1"
			      : "=a"(ret), "=m"(arg->atom)
			      : "r"(ret & mask), "m"(arg->atom), "0"(ret)
			      : "memory", "cc");
	return ret;
}

static inline long dlib_atomic_xoor(dlib_atomic_t *arg, long mask)
{
	long ret = arg->atom;
	
	__asm__ __volatile__ ("lock; cmpxchgl %2, %1"
			      : "=a"(ret), "=m"(arg->atom)
			      : "r"(ret | mask), "m"(arg->atom), "0"(ret)
			      : "memory", "cc");
	return ret;
}

static inline long dlib_atomic_xchg(dlib_atomic_t *arg, long val)
{
	__asm__ __volatile__ ("lock; xchgl %2, %1"
			      : "=r"(val), "=m"(arg->atom)
			      : "0"(val), "m"(arg->atom)
			      : "memory", "cc");
	return val;
}

static inline long dlib_atomic_cas(dlib_atomic_t *arg, long set, long cmp)
{
	long ret;
	__asm__ __volatile__ ("lock; cmpxchgl %2, %1"
			      : "=a"(ret), "=m"(arg->atom)
			      : "r"(set), "m"(arg->atom), "0"(cmp)
			      : "memory", "cc");
	return ret;
}

#else /* (defined (__i386__) || defined (__x86_64__)) && (defined (__GNUC__)) */
#define atomic_memory_barrier()
#define atomic_cpu_pause()

typedef struct dlib_atomic {
	volatile long   atom;
	dlib_lock_t     lock;
} dlib_atomic_t;

static inline int dlib_atomic_init(dlib_atomic_t *arg, long val)
{
	int ret = 0;
	if ((ret = dlib_lock_init(&arg->lock)) != 0) {
		return ret;
	}
	arg->atom = val;
	return ret;
}

static inline void dlib_atomic_exit(dlib_atomic_t *arg)
{
	dlib_lock_exit(&arg->lock);
	arg->atom = 0;
}

static inline int dlib_atomic_test(dlib_atomic_t *arg, long test)
{
	return (arg->atom == test);
}

static inline void dlib_atomic_set(dlib_atomic_t *arg, long val)
{
	arg->atom = val;
}

static inline long dlib_atomic_get(dlib_atomic_t *arg)
{
	return arg->atom;
}

static inline void dlib_atomic_inc(dlib_atomic_t *arg)
{
	dlib_lock_lock(&arg->lock);
	arg->atom += 1;
	dlib_lock_unlock(&arg->lock);
}

static inline void dlib_atomic_dec(dlib_atomic_t *arg)
{
	dlib_lock_lock(&arg->lock);
	arg->atom -= 1;
	dlib_lock_unlock(&arg->lock);
}

static inline void dlib_atomic_add(dlib_atomic_t *arg, long add)
{
	dlib_lock_lock(&arg->lock);
	arg->atom += add;
	dlib_lock_unlock(&arg->lock);
}

static inline void dlib_atomic_sub(dlib_atomic_t *arg, long sub)
{
	dlib_lock_lock(&arg->lock);
	arg->atom -= sub;
	dlib_lock_unlock(&arg->lock);
}

static inline long dlib_atomic_xadd(dlib_atomic_t *arg, long add)
{
	long ret = 0;
	dlib_lock_lock(&arg->lock);
	ret = arg->atom;
	arg->atom += add;
	dlib_lock_unlock(&arg->lock);
	return ret;
}

static inline long dlib_atomic_xsub(dlib_atomic_t *arg, long sub)
{
	long ret = 0;
	dlib_lock_lock(&arg->lock);
	ret = arg->atom;
	arg->atom -= sub;
	dlib_lock_unlock(&arg->lock);
	return ret;
}

static inline long dlib_atomic_xand(dlib_atomic_t *arg, long mask)
{
	long ret = 0;
	dlib_lock_lock(&arg->lock);
	ret = arg->atom;
	arg->atom &= mask;
	dlib_lock_unlock(&arg->lock);
	return ret;
}

static inline long dlib_atomic_xoor(dlib_atomic_t *arg, long mask)
{
	long ret = 0;
	dlib_lock_lock(&arg->lock);
	ret = arg->atom;
	arg->atom |= mask;
	dlib_lock_unlock(&arg->lock);
	return ret;
}

static inline long dlib_atomic_xchg(dlib_atomic_t *arg, long val)
{
	long ret = 0;
	dlib_lock_lock(&arg->lock);
	ret = arg->atom;
	arg->atom = val;
	dlib_lock_unlock(&arg->lock);
	return ret;
}

static inline long dlib_atomic_cas(dlib_atomic_t *arg, long set, long cmp)
{
	long ret = cmp;
	dlib_lock_lock(&arg->lock);
	if (arg->atom == cmp)
		arg->atom = set;
	else
		ret = arg->atom;
	dlib_lock_unlock(&arg->lock);
	return ret;
}
#endif

/** bit module other APIs */

/**
 * dlib_show_bytes
 * @brief Show each word of *arg
 *	int a = 0x12345678;
 *	dlib_show_bytes(&a, sizeof(int));
 * @return just print each word of *arg
 * @param arg[in]: defined as any structure
 * @param len[in]: sizeof(structure)
 */
extern void dlib_show_bytes(void *arg, uint32_t len);

	
#ifdef __cplusplus
}
#endif
#endif
